题目大意
给定一个树状的仓库分布信息，每个仓库初始有一些月饼，要求月饼通过仓库之间的联络通道（容量有限）搬运至目标状态。求出通过通道搬运的最小次数。
思路讲解
既然是树形的数据结构，遍历上就肯定要用深搜。我们看样例解释可以总结出一点小规律：
对于若干分别要放出月饼和收入月饼的仓库来说，优先匹配两个距离最近的点进行调配是最省次数的。（距离最近即从一个点到另一个点，所经过的边数最少。）
根据这个规律，可以确定一下大致思路：
- 树以任意点为根（后文为 号点），先搜索到每个叶子节点，计算出它们需要放出或收入多少月饼。
- 向它的父亲赠出或索要这些月饼（因为是树形数据结构，所以所有调配方案都要经过其父亲之手）。计算此处搬运所需次数。
- 父亲通过其他孩子赠出或索要到的月饼来调配，尽量满足刚才孩子仓库的需求。
- 若父亲也无法满足孩子的需要了，就向它的父亲继续赠出或索要。
由于保证月饼礼盒的当前总数与目标总数相同，所以此思路是完全可行的。
代码实现
搜索部分
此处使用邻接表存图。代码中 数组计算开始到结束仓库月饼的变化量。
搬运次数只与变化量绝对值和当前边单次可拿的最多数量有关，所以代码中用 abs 函数取了绝对值。当然不要忘了向上取整，若对代码中的取整方法有疑问也可以强转为小数类型，使用 ceil 函数向上取整（可能有精度问题）。
vector<pair<int,int> >a[200005];void dfs(int x,int fa){ for(int i=0;i<a[x].size();i++){ int nxt=a[x][i].first,val=a[x][i].second;//这里一定要是局部变量，否则孩子的变量值会影响到父亲导致答案错误 if(nxt!=fa){ dfs(nxt,x); cg[x]+=cg[nxt];//来自孩子的“赠予或索要” cnt+=(abs(cg[nxt])+val-1)/val;//计算搬运次数 } }}完整代码
#include<bits/stdc++.h>using namespace std;long long n,u,v,c,cnt;int s[200005],t[200005],cg[200005];vector<pair<int,int> >a[200005];void dfs(int x,int fa){ for(int i=0;i<a[x].size();i++){ int nxt=a[x][i].first,val=a[x][i].second; if(nxt!=fa){ dfs(nxt,x); cg[x]+=cg[nxt]; cnt+=(abs(cg[nxt])+val-1)/val; } }}int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>s[i]; } for(int i=1;i<=n;i++){ cin>>t[i]; cg[i]=s[i]-t[i]; } for(int i=1;i<=n-1;i++){ cin>>u>>v>>c; a[u].push_back(make_pair(v,c)); a[v].push_back(make_pair(u,c)); } dfs(1,0); cout<<cnt; return 0;}